Determine if a Sudoku is valid, according to: Sudoku Puzzles - The Rules.

The Sudoku board could be partially filled, where empty cells are filled with the character '.'.

A partially filled sudoku which is valid.

Note: A valid Sudoku board (partially filled) is not necessarily solvable. Only the filled cells need to be validated.



In [39]:

    
import pdb
class Solution(object):
    def isValidSudoku(self, board):
        """
        分别判断横行，竖行，还有9宫格的数字就好
        :type board: List[List[str]]
        :rtype: bool
        """

        # judge row
        for row in board:
            s = ''
            for c in row:
                if c in s:
                    return False
                if c != '.':
                    s += c
    
        # judge column
        for j in range(9):
            col = ''
            for i in range(9):
                if board[i][j] in col:
                    return False
                if board[i][j] != '.':
                    col += board[i][j]
            
                    
        row_column = [(0, 0), (0, 3), (0, 6), (3, 0), (3, 3), (3, 6), (6, 0), (6, 3), (6, 6)]
        for d in row_column:
            i, j = d
            s = ''
            for ti in range(3):
                for tj in range(3):
                    if board[i+ti][j+tj] in s:
                        return False
                    if board[i+ti][j+tj] != '.':
                        s += board[i+ti][j+tj]
        return True



In [40]:

    
Solution().isValidSudoku(["..4...63.",".........","5......9.","...56....","4.3.....1","...7.....","...5.....",".........","........."])









    Out[40]:





False



In [41]:

    
# judge column
Solution().isValidSudoku([".87654321","2........","3........","4........","5........","6........","7.....4..","8......4.","9........"])









    Out[41]:





False



In [42]:

    
# judge column
Solution().isValidSudoku([".87654321","2........","3........","4........","5........","6........","7........","8........","9.......1"])









    Out[42]:





False



In [43]:

    
# judge row
Solution().isValidSudoku([".87654321","2........","3........","4........","5........","6........","7........","8........","9........"])









    Out[43]:





True



In [44]:

    
class Solution:
    # @param board, a 9x9 2D array
    # @return a boolean
    def isValidSudoku(self, board):
        """
        使用3个list，每个list包含9个set
        """ 
        row = [set([]) for i in range(9)]
        col = [set([]) for i in range(9)]
        grid = [set([]) for i in range(9)]

        for r in range(9):
            for c in range(9):
                if board[r][c] == '.':
                    continue
                if board[r][c] in row[r]:
                    return False
                if board[r][c] in col[c]:
                    return False

                g = r / 3 * 3 + c / 3
                if board[r][c] in grid[g]:
                    return False
                grid[g].add(board[r][c])
                row[r].add(board[r][c])
                col[c].add(board[r][c])

        return True



In [ ]: